package leetcode.lt题型分类.差分数组;

import leetcode.每日一题.奇偶树;
import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2022/10/15 9:23 PM
 * @description：https://leetcode.cn/problems/hand-of-straights/
 */
public class 一手顺子 {
    @Test
    public void test() {
        System.out.println(new Solution().isNStraightHand(new int[]{1, 2, 3, 6, 2, 3, 4, 7, 8}, 3));
    }

    /*class Solution {
        public boolean isNStraightHand(int[] hand, int groupSize) {
            Map<Integer, Integer> map = new HashMap<>();
            Arrays.sort(hand);
            for (int h : hand) {
                map.put(h, map.getOrDefault(h, 0) + 1);
            }
            for (int h : hand) {
                if (map.get(h) == 0) continue;
                map.put(h, map.get(h) - 1);
                for (int i = 1; i < groupSize; i++) {
                    int cnt = map.getOrDefault(h + i, 0);
                    if (cnt == 0) return false;
                    map.put(h + i, cnt - 1);
                }
            }
            return true;
        }
    }*/

    class Solution {
        public boolean isNStraightHand(int[] hand, int groupSize) {
            Map<Integer, Integer> map = new HashMap<>();
            PriorityQueue<Integer> q = new PriorityQueue<>(Comparator.comparingInt(a -> a));
            for (int h : hand) {
                map.put(h, map.getOrDefault(h, 0) + 1);
                q.add(h);
            }
            while (!q.isEmpty()) {
                int cur = q.poll();
                if (map.get(cur) == 0) continue;;
                map.put(cur, map.get(cur) - 1);
                for (int i = 1; i < groupSize; i++) {
                    int cnt = map.getOrDefault(cur + i, 0);
                    if (cnt == 0) return false;
                    map.put(cur + i, cnt - 1);
                }
            }
            return true;
        }
    }
}
